package 系统复习.链表;

import datastructure.ListNode;

/**
 * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 *
 * 双指针、递归、头插、堆栈方式
 */


public class L206 {

    public static ListNode reverseList(ListNode head) {

        // 双指针
        /*ListNode prev = null;
        ListNode cur = head;
        ListNode temp = null;
        while (cur != null) {
            temp = cur.next;// 保存下一个节点
            cur.next = prev;
            prev = cur;
            cur = temp;
        }
        return prev;*/

        // 递归
//        return reverse(null, head);


        // 边缘条件判断 从后向前递归
        if(head == null) return null;
        if (head.next == null) return head;

        // 递归调用，翻转第二个节点开始往后的链表
        ListNode last = reverseList(head.next);
        // 翻转头节点与第二个节点的指向
        head.next.next = head;
        // 此时的 head 节点为尾节点，next 需要指向 NULL
        head.next = null;
        return last;

    }

    private ListNode reverse(ListNode prev, ListNode cur) {
        if (cur == null) {
            return prev;
        }
        ListNode temp = null;
        temp = cur.next;// 先保存下一个节点
        cur.next = prev;// 反转
        // 更新prev、cur位置
        // prev = cur;
        // cur = temp;
        return reverse(cur, temp);
    }


    public static void main(String[] args) {
        ListNode listNode = ListNode.buildList(new int[]{1, 2, 3, 4, 5});
        ListNode head = reverseList(listNode);
        ListNode.printListNode(head);
    }

}
